{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二进制求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addBinary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个 01 字符串&nbsp;<code>a</code>&nbsp;和&nbsp;<code>b</code>&nbsp;，请计算它们的和，并以二进制字符串的形式输出。</p>\n",
    "\n",
    "<p>输入为 <strong>非空 </strong>字符串且只包含数字&nbsp;<code>1</code>&nbsp;和&nbsp;<code>0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> a = &quot;11&quot;, b = &quot;10&quot;\n",
    "<strong>输出:</strong> &quot;101&quot;</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> a = &quot;1010&quot;, b = &quot;1011&quot;\n",
    "<strong>输出:</strong> &quot;10101&quot;</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个字符串仅由字符 <code>&#39;0&#39;</code> 或 <code>&#39;1&#39;</code> 组成。</li>\n",
    "\t<li><code>1 &lt;= a.length, b.length &lt;= 10^4</code></li>\n",
    "\t<li>字符串如果不是 <code>&quot;0&quot;</code> ，就都不含前导零。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 67&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/add-binary/\">https://leetcode-cn.com/problems/add-binary/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [JFETK5](https://leetcode.cn/problems/JFETK5/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [JFETK5](https://leetcode.cn/problems/JFETK5/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        # 转十进制\n",
    "        x, y = int(a, 2), int(b, 2)\n",
    "        while y:\n",
    "            # 模拟加法运算\n",
    "            ans = x ^ y\n",
    "            y = (x & y) << 1\n",
    "            x = ans\n",
    "        # 返回二进制\n",
    "        return bin(x)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res=int(a,2)+int(b,2)\n",
    "        if res==0:\n",
    "            return '0'\n",
    "        def binary(s):\n",
    "            tmp=[0 for i in range(10000)]\n",
    "            for i in range(len(tmp)):\n",
    "                tmp[i]=str(s%2)\n",
    "                s=s//2\n",
    "            tmp.reverse()\n",
    "            idx=tmp.index('1')\n",
    "            tmp=tmp[idx:]\n",
    "            return ''.join(tmp)\n",
    "        print(binary(res))\n",
    "        return binary(res)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return '{:b}'.format(int(a,2)+int(b,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        len_a, len_b = len(a), len(b)\n",
    "        i, j, k = len_a - 1, len_b - 1, 0\n",
    "\n",
    "        maxn = 10 ** 4 + 5\n",
    "        ret = [0] * maxn\n",
    "        while i >= 0 or j >= 0:\n",
    "            if i >= 0 and j >= 0:\n",
    "                ret[k] = int(a[i]) + int(b[j])\n",
    "            elif i >= 0:\n",
    "                ret[k] = int(a[i])\n",
    "            else:\n",
    "                ret[k] = int(b[j])\n",
    "            \n",
    "            k += 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        k = 0\n",
    "        while k < maxn:\n",
    "            if ret[k] == 2:\n",
    "                ret[k] = 0\n",
    "                ret[k + 1] += 1\n",
    "            elif ret[k] == 3:\n",
    "                ret[k] = 1\n",
    "                ret[k + 1] += 1\n",
    "            \n",
    "            k += 1\n",
    "\n",
    "        ret = [str(x) for x in ret]\n",
    "        ret = ''.join(reversed(ret))\n",
    "        k = 0\n",
    "        while k < maxn and ret[k] == '0':\n",
    "            k += 1\n",
    "        \n",
    "        return ret[k:] if k != maxn else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        def add(x, y, z):\n",
    "            if x == y == '0':\n",
    "                return z, '0' \n",
    "            \n",
    "            if x == y == '1':\n",
    "                return z, '1'\n",
    "            \n",
    "            if z == '0':\n",
    "                return '1', '0'\n",
    "            \n",
    "            return '0', '1'\n",
    "\n",
    "\n",
    "        res = ''\n",
    "        diff = abs(len(a)-len(b))\n",
    "        if len(a) < len(b):\n",
    "            a = '0'*diff + a\n",
    "        else:\n",
    "            b = '0'*diff + b\n",
    "        \n",
    "        x = '0'\n",
    "        for i in range(1, len(a)+ 1):\n",
    "            y, x = add(a[-i], b[-i], x)\n",
    "            res = y+res\n",
    "        \n",
    "        \n",
    "\n",
    "        return res if x == '0' else f'1{res}'\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        alen = len(a)\n",
    "        blen = len(b)\n",
    "        end1 = alen - 1\n",
    "        end2 = blen - 1\n",
    "        res1 = 0\n",
    "        mod1 = 0\n",
    "        res2 = 0\n",
    "        mod2 = 0\n",
    "        while end1 >= 0:\n",
    "            res1 += int(a[end1]) * 2 ** mod1\n",
    "            end1 -= 1\n",
    "            mod1 += 1\n",
    "        while end2 >= 0:\n",
    "            res2 += int(b[end2]) * 2 ** mod2\n",
    "            end2 -= 1\n",
    "            mod2 += 1\n",
    "        return bin(res1+res2).split('0b')[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res, count = '', 0\n",
    "        i, j = len(a) - 1, len(b) - 1\n",
    "        while i >= 0 or j >= 0 or count:\n",
    "            if i >= 0:\n",
    "                count += int(a[i])\n",
    "            if j >= 0:\n",
    "                count += int(b[j])\n",
    "            res += str(count % 2)\n",
    "            count //= 2 # 逢二进一\n",
    "            i, j = i - 1, j - 1\n",
    "        return res[::-1] # 倒序输出\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        add_more = 0\n",
    "        if len(a) < len(b):\n",
    "            a, b = b, a\n",
    "        \n",
    "        ans = ''\n",
    "        index = -1\n",
    "        while index >= -len(a):\n",
    "            tmp_b = int(b[index]) if index >= -len(b) else 0\n",
    "            cur_sum = add_more + int(a[index]) + tmp_b\n",
    "            add_more = cur_sum // 2\n",
    "            cur_sum %= 2\n",
    "            ans = str(cur_sum) + ans\n",
    "            index -= 1\n",
    "        \n",
    "        if add_more == 1:\n",
    "            ans = str(1) + ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return'{0:b}'.format(int(a,2)+int(b,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "\n",
    "        max_len = max(len(a), len(b))\n",
    "        a = a.zfill(max_len)\n",
    "        b = b.zfill(max_len)\n",
    "\n",
    "        carry = 0 \n",
    "        result = ''\n",
    "\n",
    "        for i in range(max_len-1, -1, -1):\n",
    "            s = int(a[i]) + int(b[i]) + carry\n",
    "\n",
    "            if s >= 2:\n",
    "                carry = 1\n",
    "                s -= 2\n",
    "            else:\n",
    "                carry = 0 \n",
    "            result = str(s) + result   \n",
    "\n",
    "        if carry == 1:\n",
    "            result = '1' + result\n",
    "\n",
    "        return result  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        cur = 0 # 游标\n",
    "        res = ''\n",
    "        i, j = len(a) - 1, len(b) - 1\n",
    "        while i >= 0 or j >= 0 or cur:\n",
    "            if i >= 0:\n",
    "                cur += int(a[i])\n",
    "            if j >= 0:\n",
    "                cur += int(b[j])\n",
    "            res += str(cur % 2)\n",
    "            cur //= 2\n",
    "            i, j = i - 1, j - 1\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res = []\n",
    "        i = len(a) - 1\n",
    "        j = len(b) - 1\n",
    "        \n",
    "        carry = 0\n",
    "        while(i >= 0 or j >= 0):\n",
    "            p = a[i] if i >= 0 else 0\n",
    "            q = b[j] if j >= 0 else 0\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            sum = int(p) + int(q) + carry\n",
    "            if sum < 2:\n",
    "                carry = 0\n",
    "            elif sum == 2:\n",
    "                sum = 0\n",
    "                carry = 1\n",
    "            else:\n",
    "                sum = 1\n",
    "                carry = 1\n",
    "            res.append(str(sum))\n",
    "        \n",
    "        if carry == 1:\n",
    "            res.append(\"1\")\n",
    "        res.reverse()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2)+int(b,2))[2:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2)+int(b,2))[2:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        f1, f2 = list(a), list(b)\n",
    "        f1.reverse()\n",
    "        f2.reverse()\n",
    "        # print(f1, f2)\n",
    "        l1, l2 = len(f1), len(f2)\n",
    "        l = max(l1, l2)\n",
    "        adv = 0\n",
    "        ret = []\n",
    "        for i in range(l):\n",
    "            a = int(f1[i]) if i < l1 else 0\n",
    "            b = int(f2[i]) if i < l2 else 0\n",
    "            val = a + b + adv\n",
    "            m = val % 2\n",
    "            adv = val // 2\n",
    "            ret.insert(0, str(m))\n",
    "        if adv != 0:\n",
    "            ret.insert(0, str(adv))\n",
    "        return \"\".join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        if len(a) < len(b):\n",
    "            a, b = b, a\n",
    "        lst_1 = [int(ch) for ch in a]\n",
    "        lst_2 = [int(ch) for ch in b]\n",
    "        lst_2 = [0] * (len(lst_1) - len(lst_2)) + lst_2\n",
    "        ans = [\"0\"] * (len(lst_2) + 1)\n",
    "        _tmp = 0\n",
    "        for i in range(len(lst_1) - 1, -1, -1):\n",
    "            _total = lst_2[i] + lst_1[i] + _tmp\n",
    "            ans[i + 1] = str(_total % 2)\n",
    "            _tmp = _total // 2\n",
    "        ans[0] = str(_tmp)\n",
    "\n",
    "        return \"\".join(ans) if ans[0]!=\"0\" else \"\".join(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        x, y = int(a, 2), int(b, 2)\n",
    "        while y:\n",
    "            answer = x ^ y\n",
    "            carry = (x & y) << 1\n",
    "            x, y = answer, carry\n",
    "        return bin(x)[2:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res = str(bin(int(a,2) + int(b,2)))[2:]   # int(a, 2) 把2进制的a转换成10进制的，bin()转化成二进制\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return '{0:b}'.format(int(a, 2) + int(b, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def addBinary(self, a, b):\n",
    "        res = \"\"\n",
    "        carry = 0\n",
    "        i = len(a) - 1\n",
    "        j = len(b) - 1\n",
    "        while i >= 0 or j >= 0 or carry != 0:\n",
    "            digitA = int(a[i]) if i >= 0 else 0\n",
    "            digitB = int(b[j]) if j >= 0 else 0\n",
    "            sum = digitA + digitB + carry\n",
    "            carry = 1 if sum >= 2 else 0\n",
    "            sum = sum - 2 if sum >= 2 else sum\n",
    "            res += str(sum)\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        return res[::-1]\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return '{0:b}'.format(int(a, 2) + int(b, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a=int(a,2)\n",
    "        b=int(b,2)\n",
    "        c=a+b\n",
    "        c=bin(c)[2:]\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a1 = 0\n",
    "        power = 0\n",
    "        for i, v in enumerate(a[::-1]):\n",
    "            a1 += int(v) * (2**power)\n",
    "            power += 1\n",
    "        b1 = 0\n",
    "        power = 0\n",
    "        for i, v in enumerate(b[::-1]):\n",
    "            b1 += int(v) *(2**power)\n",
    "            power += 1\n",
    "        res = a1 + b1\n",
    "        return bin(res)[2:]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a = int(a,2)\n",
    "        b = int(b,2)\n",
    "        return bin(a + b)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a=int(a,2)   # int可以将字符串转二进制数\n",
    "        b=int(b,2)    \n",
    "        c=a+b\n",
    "        c=bin(c)[2:]  # 将十进制转换成二进制，并且是字符串形式\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        ans = ''\n",
    "        carry = 0\n",
    "        for ch1, ch2 in zip_longest(reversed(a), reversed(b), fillvalue='0'):\n",
    "            carry += int(ch1) + int(ch2)\n",
    "            ans += '1' if carry % 2 else '0'\n",
    "            carry //= 2\n",
    "        if carry:\n",
    "            ans += '1'\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return str(bin(int(a, 2)+int(b, 2)))[2:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a, b) -> str:\n",
    "        return '{0:b}'.format(int(a, 2) + int(b, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return str(bin(int(a, 2) + int(b, 2)))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        ans = []\n",
    "        n = max(len(a), len(b))\n",
    "        carry = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            carry += int(a[-1 - i]) if i < len(a) else 0\n",
    "            carry += int(b[-1 - i]) if i < len(b) else 0\n",
    "            ans.append(str(carry % 2))\n",
    "            carry //= 2\n",
    "        if carry > 0:\n",
    "            ans.append(str(1))\n",
    "        ans.reverse()\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "         return '{0:b}'.format(int(a, 2) + int(b, 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a, 2)+int(b,2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return str(bin(int(a, 2)+int(b, 2)))[2:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a, 2) + int(b, 2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        x, y = int(a, 2), int(b, 2)\n",
    "        while y:\n",
    "            answer = x ^ y\n",
    "            carry = (x & y) << 1\n",
    "            x, y = answer, carry\n",
    "        return bin(x)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a,2)+int(b,2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        n, m = len(a), len(b)\n",
    "        flag = 0\n",
    "        i, j = n-1, m-1\n",
    "        ans = ''\n",
    "        while i >= 0 and j >= 0:\n",
    "            if a[i] == '0' and b[j] == '0':\n",
    "                ans = str(flag) + ans\n",
    "                flag = 0\n",
    "            elif a[i] == '1' and b[j] == '1':\n",
    "                ans = str(flag) + ans\n",
    "                flag = 1\n",
    "            else:\n",
    "                if flag == 0:\n",
    "                    ans = '1' + ans\n",
    "                    flag = 0\n",
    "                else:\n",
    "                    ans = '0' + ans\n",
    "                    flag = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        while i >= 0:\n",
    "            if a[i] == '1' and flag == 1:\n",
    "                ans = '0' + ans\n",
    "                flag = 1\n",
    "            elif a[i] == '0' and flag == 0:\n",
    "                ans = '0' + ans\n",
    "                flag = 0\n",
    "            else:\n",
    "                ans = '1' + ans\n",
    "                flag = 0\n",
    "            i -= 1\n",
    "        while j >= 0:\n",
    "            if b[j] == '1' and flag == 1:\n",
    "                ans = '0' + ans\n",
    "                flag = 1\n",
    "            elif b[j] == '0' and flag == 0:\n",
    "                ans = '0' + ans\n",
    "                flag = 0\n",
    "            else:\n",
    "                ans = '1' + ans\n",
    "                flag = 0\n",
    "            j -= 1\n",
    "        \n",
    "        if flag:\n",
    "            ans = '1' + ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        carry = 0\n",
    "        m = len(a)\n",
    "        n = len(b)\n",
    "        m -= 1\n",
    "        n -= 1\n",
    "        list = []\n",
    "        while m>=0 and n>=0:\n",
    "            moda = int(a[m])\n",
    "            modb = int(b[n])\n",
    "            sum = moda+modb+carry\n",
    "            if sum>=2:\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            list.append(str(sum%2))\n",
    "            m -= 1\n",
    "            n -= 1\n",
    "        while m>=0:\n",
    "            moda = int(a[m])\n",
    "            sum = moda+carry\n",
    "            if sum>=2:\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            list.append(str(sum%2))\n",
    "            m -= 1\n",
    "        while n>=0:\n",
    "            modb = int(b[n])\n",
    "            sum = modb+carry\n",
    "            if sum>=2:\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            list.append(str(sum%2))\n",
    "            n -= 1\n",
    "        if carry==1:\n",
    "            list.append(str(carry))\n",
    "        list.reverse()\n",
    "        return \"\".join(str(x) for x in list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        1 <= len(a) , len(b) <= 10**4\n",
    "        c=int(\"0b\"+a,2)+int(\"0b\"+b,2)\n",
    "        d=bin(c)[2:]\n",
    "        return d\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def addBinary(self, a: str, b: str) -> str:\r\n",
    "        n_len = max(len(a), len(b))\r\n",
    "        c = \"\"\r\n",
    "        condition = 0\r\n",
    "        for i in range(1, n_len+1):\r\n",
    "            if i <= len(a):\r\n",
    "                left = int(a[-i])\r\n",
    "            else:\r\n",
    "                left = 0\r\n",
    "            if i <= len(b):\r\n",
    "                right = int(b[-i])\r\n",
    "            else:\r\n",
    "                right = 0\r\n",
    "            if left + right + condition == 2:\r\n",
    "                c += \"0\"\r\n",
    "                condition = 1\r\n",
    "            elif left + right + condition == 3:\r\n",
    "                c += \"1\"\r\n",
    "                condition = 1\r\n",
    "            elif left + right + condition == 1:\r\n",
    "                c += \"1\"\r\n",
    "                condition = 0\r\n",
    "            else:\r\n",
    "                c += \"0\"\r\n",
    "                condition = 0\r\n",
    "        if condition == 1:\r\n",
    "            c += \"1\"\r\n",
    "        return c[::-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        bit_str_list = []\n",
    "\n",
    "        # 从字符串最后一位往第0位累加\n",
    "        idx_a, idx_b = len(a) - 1, len(b) - 1\n",
    "        plus = 0\n",
    "        while idx_a >= 0 and idx_b >= 0:\n",
    "            bit_a, bit_b = int(a[idx_a]), int(b[idx_b])\n",
    "            bit_str_list.append(str(bit_a ^ bit_b ^ plus))\n",
    "\n",
    "            if bit_a + bit_b + plus > 1:\n",
    "                plus = 1\n",
    "            else:\n",
    "                plus = 0\n",
    "            \n",
    "            idx_a -= 1\n",
    "            idx_b -= 1\n",
    "\n",
    "        # 处理还没有到第0位的idx\n",
    "        for idx, s in [(idx_a, a), (idx_b, b)]:\n",
    "            while idx >= 0:\n",
    "                bit = int(s[idx])\n",
    "                bit_str_list.append(str(bit ^ plus))\n",
    "\n",
    "                if bit + plus > 1:\n",
    "                    plus = 1\n",
    "                else:\n",
    "                    plus = 0\n",
    "                \n",
    "                idx -= 1\n",
    "\n",
    "        # 处理进位\n",
    "        if plus:\n",
    "            bit_str_list.append(str(plus))\n",
    "\n",
    "        # 将字符反转后返回\n",
    "        return \"\".join(bit_str_list[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        m1,m2=len(a),len(b)\n",
    "        m=max(m1,m2)\n",
    "        a='0'*(m-m1)+a\n",
    "        b='0'*(m-m2)+b\n",
    "        c=''\n",
    "        temp=0\n",
    "        for i in range(m):\n",
    "            x=int(a[-1-i])\n",
    "            y=int(b[-1-i])\n",
    "            if x+y+temp>=2:\n",
    "                c=str(x+y+temp-2)+c\n",
    "                temp=1\n",
    "            else:\n",
    "                c=str(x+y+temp)+c\n",
    "                temp=0\n",
    "        c=c if temp==0 else '1'+c\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        la,lb = list(a) ,list(b)\n",
    "        la.reverse()\n",
    "        lb.reverse()\n",
    "        max1= max(len(a),len(b))\n",
    "        diff = [\"0\"]*abs(len(a) - len(b))\n",
    "\n",
    "        if len(a)> len(b):\n",
    "            lb.extend(diff)\n",
    "        else:\n",
    "            la.extend(diff)\n",
    "\n",
    "        flag = 0\n",
    "        result = []\n",
    "        for i in range(max1):\n",
    "            temp = int(la[i])+int(lb[i])+flag\n",
    "            if temp >=2:\n",
    "                flag= 1\n",
    "            else:\n",
    "                flag = 0\n",
    "            result.append(str(temp % 2))\n",
    "        if flag ==1:\n",
    "            result.append(\"1\")\n",
    "        result.reverse()\n",
    "        return \"\".join(result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        ret,count = '',0 # 定义一个空的字符串\n",
    "        i,j = len(a)-1,len(b)-1\n",
    "        while i >= 0 or j >= 0 or count:\n",
    "            if i >= 0: count += ord(a[i]) - ord('0') # ord()用于获取字符串的数字值\n",
    "            if j >= 0: count += ord(b[j]) - ord('0')\n",
    "            ret += str(count % 2)\n",
    "            count //= 2\n",
    "            i,j = i-1,j-1\n",
    "        return ret[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        same_len = max(len(a), len(b))\n",
    "        b_num1 = a.rjust(same_len, \"0\")\n",
    "        b_num2 = b.rjust(same_len, \"0\")\n",
    "\n",
    "        res = []\n",
    "\n",
    "        up_mark = 0\n",
    "        for i in range(len(b_num1) - 1, -1, -1):\n",
    "            bit_1 = int(b_num1[i])\n",
    "            bit_2 = int(b_num2[i])\n",
    "            sum = bit_1 + bit_2 + up_mark\n",
    "\n",
    "            up_mark = sum // 2 == 1\n",
    "            res.append(str(sum % 2))\n",
    "\n",
    "            if i == 0 and up_mark:\n",
    "                res.append('1')\n",
    "\n",
    "        res.reverse()\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        x, y = int(a, 2), int(b, 2)\n",
    "        while y > 0:\n",
    "            ans = x ^ y\n",
    "            carry = (x & y) << 1\n",
    "            x, y = ans, carry\n",
    "        return bin(x)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res = ''\n",
    "        i, j = len(a)-1, len(b)-1\n",
    "        carry = 0\n",
    "        while i>=0 or j>=0:\n",
    "            x = int(a[i]) if i>=0 else 0\n",
    "            y = int(b[j]) if j>=0 else 0\n",
    "\n",
    "            sum = x + y + carry\n",
    "            res += str(sum%2)\n",
    "            carry = sum // 2\n",
    "\n",
    "            i, j = i-1, j-1\n",
    "            print(carry, sum, res)\n",
    "        \n",
    "        if carry!=0: res += str(carry)\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return '{0:b}'.format(int(a, 2) + int(b, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        if len(a)>len(b):\n",
    "            a,b=b,a\n",
    "        a=a.zfill(len(b))\n",
    "        carry=0\n",
    "        ans=''\n",
    "        for i in range(-1,-len(a)-1,-1):\n",
    "            m = int(a[i])+int(b[i])+carry\n",
    "            carry=m//2\n",
    "            n=m%2\n",
    "            ans=str(n) + ans\n",
    "        if carry!=0:\n",
    "            ans=str(carry)+ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return str(bin(int(a, 2) + int(b, 2)))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        def to2(val):\n",
    "            res=[]\n",
    "            while(val):\n",
    "                res.append(str(val%2))\n",
    "                val=val//2\n",
    "            res.reverse()\n",
    "\n",
    "            return ''.join(res)\n",
    "        def to10(stri):\n",
    "            lt=list(stri)\n",
    "            lt.reverse()\n",
    "            res=0\n",
    "            for i in range(len(lt)):\n",
    "                res+=int(lt[i])*2**i\n",
    "            return res\n",
    "        a10,b10=to10(a),to10(b)\n",
    "        print(a10,b10)\n",
    "        c=a10+b10\n",
    "        if to2(c)==\"\": return \"0\"\n",
    "        return to2(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        if len(a) < len(b):\n",
    "            a, b = b, a\n",
    "        l1 = len(a)-1\n",
    "        l2 = len(b)-1\n",
    "        a = list(a)\n",
    "        b = list(b)\n",
    "        while l2>=0:\n",
    "            a[l1] = str(int(b[l2]) + int(a[l1]))\n",
    "            l1 -= 1\n",
    "            l2 -= 1\n",
    "        a.insert(0, '0')\n",
    "        for i in range(len(a)-1, -1, -1):\n",
    "            if a[i] > '1':\n",
    "                a[i] = str(int(a[i]) - 2)\n",
    "                a[i-1] = str(int(a[i-1]) + 1)\n",
    "        print(a)\n",
    "        if a[0] == '0':\n",
    "            return \"\".join(a[1:])\n",
    "        return \"\".join(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        la, lb = len(a)-1, len(b)-1\n",
    "        rs = \"\"\n",
    "        bit_tmp = 0\n",
    "        while la>=0 or lb>=0:\n",
    "            bit_a = int(a[la]) if la>=0 else 0\n",
    "            bit_b = int(b[lb]) if lb>=0 else 0\n",
    "            cur_sum = bit_a+bit_b+bit_tmp  # 当前和\n",
    "            bit_tmp = cur_sum//2  # 进位\n",
    "            cur_bit = cur_sum%2  # 当前位\n",
    "            rs = str(cur_bit) + rs\n",
    "            la -= 1\n",
    "            lb -= 1\n",
    "        if bit_tmp==1:\n",
    "            rs = \"1\" + rs\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a=int(a,2)   # int可以将字符串转二进制数\n",
    "        b=int(b,2)    \n",
    "        \n",
    "        c=bin(a+b)[2:]  # 将十进制转换成二进制，并且是字符串形式\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "\n",
    "        return '{0:b}'.format(int(a, 2) + int(b, 2)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        res, count = '', 0\n",
    "        i, j = len(a) - 1, len(b) - 1\n",
    "        while i >= 0 or j >= 0 or count: # 如果count不为0, 说明还需要再进一位\n",
    "            if i >= 0:\n",
    "                count += int(a[i])\n",
    "            if j >= 0:\n",
    "                count += int(b[j])\n",
    "            res += str(count % 2)\n",
    "            count //= 2 # 逢二进一\n",
    "            i, j = i - 1, j - 1\n",
    "        return res[::-1] # 倒序输出\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        # 将两个二进制数转换为列表\n",
    "        a = list(a)\n",
    "        b = list(b)\n",
    "\n",
    "        # 将两个二进制数的长度补齐\n",
    "        while len(a) < len(b):\n",
    "            a.insert(0, '0')\n",
    "        while len(b) < len(a):\n",
    "            b.insert(0, '0')\n",
    "\n",
    "        # 初始化进位和结果列表\n",
    "        carry = 0\n",
    "        result = []\n",
    "\n",
    "        # 从右往左遍历两个二进制数\n",
    "        for i in range(len(a) - 1, -1, -1):\n",
    "            # 计算当前位的和\n",
    "            s = int(a[i]) + int(b[i]) + carry\n",
    "\n",
    "            # 如果和为2或3，则需要进位\n",
    "            if s == 2 or s == 3:\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "\n",
    "            # 将当前位的和加入结果列表\n",
    "            result.insert(0, str(s % 2))\n",
    "\n",
    "        # 如果最高位有进位，则需要在结果列表最前面加上1\n",
    "        if carry == 1:\n",
    "            result.insert(0, '1')\n",
    "\n",
    "        # 将结果列表转换为字符串并返回\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        return bin(int(a, 2) + int(b, 2))[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        ans = \"\"\n",
    "        n, m = len(a), len(b)\n",
    "        i, j = n-1, m-1\n",
    "        t, c = 0, 0\n",
    "        x = n if n > m else m\n",
    "        while i >= 0 or j >= 0:\n",
    "            if (x == n and j >= 0) or (x == m and i >= 0):\n",
    "                t = int(a[i]) ^ int(b[j]) ^ c\n",
    "                f =int(a[i]) + int(b[j]) + c\n",
    "                c = 1 if f >= 2 else 0\n",
    "            elif x == n:\n",
    "                t = int(a[i]) ^ c\n",
    "                c = int(a[i]) & c\n",
    "            elif x == m:\n",
    "                t = int(b[j]) ^ c\n",
    "                c = int(b[j]) & c\n",
    "            ans = str(t) + ans\n",
    "            print(t, c, ans)\n",
    "            if i >= 0:\n",
    "                i -= 1\n",
    "            if j >= 0:\n",
    "                j -= 1\n",
    "\n",
    "        if c == 1:\n",
    "            ans = str(c) + ans\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        x,y=int(a,2),int(b,2)\n",
    "        while y:\n",
    "            answer=x^y\n",
    "            carry=(x&y)<<1\n",
    "            x,y=answer,carry\n",
    "        return bin(x)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a,b = list(a),list(b)\n",
    "        m,n = len(a),len(b)\n",
    "        if m>n:\n",
    "            a,b=b,a\n",
    "            m,n=n,m\n",
    "        t = deque()\n",
    "        c=0\n",
    "        i,j=m-1,n-1\n",
    "        while i >=0:\n",
    "            if c==1:\n",
    "                if a[i]==\"1\" and b[j]==\"1\":\n",
    "                    c=1\n",
    "                    t.appendleft(\"1\")\n",
    "                elif a[i]==\"1\":\n",
    "                    c=1\n",
    "                    t.appendleft(\"0\")\n",
    "                elif b[j]==\"1\":\n",
    "                    c=1\n",
    "                    t.appendleft(\"0\")\n",
    "                else:\n",
    "                    c=0\n",
    "                    t.appendleft(\"1\")\n",
    "            else:\n",
    "                if a[i]==\"1\" and b[j]==\"1\":\n",
    "                    c=1\n",
    "                    t.appendleft(\"0\")\n",
    "                elif a[i]==\"1\":\n",
    "                    c=0\n",
    "                    t.appendleft(\"1\")\n",
    "                elif b[j]==\"1\":\n",
    "                    c=0\n",
    "                    t.appendleft(\"1\")\n",
    "                else:\n",
    "                    c=0\n",
    "                    t.appendleft(\"0\")\n",
    "            i-=1\n",
    "            j-=1\n",
    "        \n",
    "        while j>=0:\n",
    "            if c==1:\n",
    "                if b[j]==\"1\":\n",
    "                    c=1\n",
    "                    t.appendleft(\"0\")\n",
    "                else:\n",
    "                    c=0\n",
    "                    t.appendleft(\"1\")\n",
    "            else:\n",
    "                if b[j]==\"1\":\n",
    "                    c=0\n",
    "                    t.appendleft(\"1\")\n",
    "                else:\n",
    "                    c=0\n",
    "                    t.appendleft(\"0\")\n",
    "            j-=1\n",
    "        if c:\n",
    "            t.appendleft(\"1\")\n",
    "        return \"\".join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        max_len = max(len(a), len(b))  \n",
    "        a = a.zfill(max_len) # 在 a 的前面补零，使其长度与 b 相同  \n",
    "        b = b.zfill(max_len) # 在 b 的前面补零，使其长度与 a 相同  \n",
    "        \n",
    "        result = ''  \n",
    "        carry = 0  \n",
    "        for i in range(max_len - 1, -1, -1):  \n",
    "            temp = carry  \n",
    "            temp += 1 if a[i] == '1' else 0  \n",
    "            temp += 1 if b[i] == '1' else 0  \n",
    "            result = ('1' if temp % 2 == 1 else '0') + result  \n",
    "            carry = 0 if temp < 2 else 1       \n",
    "        if carry != 0: result = '1' + result  \n",
    "        return result  \n",
    "  \n",
    "\n",
    "                 \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        def BinaryAddition(pre,fin):\n",
    "            #转换为二进制\n",
    "            pre=int(a,2)\n",
    "            fin=int(b,2)\n",
    "            while fin!=0:\n",
    "                carry=pre & fin\n",
    "                pre = pre ^ fin\n",
    "                fin=carry <<1\n",
    "            return bin(pre)[2:]\n",
    "        return BinaryAddition(a,b)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        l, r, d = len(a) - 1, len(b) - 1, 0\n",
    "        ret = []\n",
    "        while l >= 0 or r >= 0:\n",
    "            f = 0\n",
    "            if l >= 0:\n",
    "                f += int(a[l])\n",
    "            \n",
    "            if r >= 0:\n",
    "                f += int(b[r])\n",
    "            f += d\n",
    "            ret.append(str(f % 2))\n",
    "            d = f // 2\n",
    "            l -= 1\n",
    "            r -= 1\n",
    "        if d > 0:\n",
    "            ret.append(\"1\")\n",
    "        return \"\".join(ret[::-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
